//
// GPSMapEdit
// (c) Konstantin Galichsky (kg@geopainting.com), 2002-2007
// (c) Nikita Karnauhov (jinx@ac-sw.com), 2006
//
// Map generalization.
//

# include "GeneralizeMap.h"
# include "StdAfx.h"
# include "GeneralizeRgn.h"
# include "Generalize.h"
# include "SetElementPoints.h"
# include "Map.h"
# include "Status.h"
# include "Globals.h"

# include <numeric>

struct edge_t {
	size_t cPolygonIndex, cStartPoint, cEndPoint;

	edge_t (size_t _cPolygonIndex, size_t _cStartPoint, size_t _cEndPoint) :
		cPolygonIndex (_cPolygonIndex),
		cStartPoint (_cStartPoint),
		cEndPoint (_cEndPoint)
	{}
};

enum point_type_t {ptNONE, ptSTART_POINT, ptEND_POINT, ptSINGLE_POINT};

struct point_rec_t {
	size_t cPolygonIndex, cIndex;
	point_type_t type;

	point_rec_t (size_t _cPolygonIndex, size_t _cIndex, point_type_t _type = ptNONE) :
		cPolygonIndex (_cPolygonIndex), cIndex (_cIndex), type (_type)
	{}
};

typedef std::set<size_t> int_set_t;
typedef std::pair<size_t, size_t> int_pair_t;
typedef std::multimap<int_pair_t, edge_t> edges_t;
typedef std::list<point_rec_t> point_list_t;
typedef std::vector<point_list_t> vec_point_to_element_t;
typedef std::vector<rgn_element_t *> element_vec_t;

// Stitching related

// Pair of adjacent edges
typedef std::pair<edge_t, edge_t> edge_pair_t;

// Meant to store edges of polygons that will be stitched together into one
typedef std::list<edge_pair_t> edge_bucket_t;

// Storage of the above
typedef std::vector<edge_bucket_t> edge_buckets_t;

// Maps polygon indices to their appropriate buckets
typedef std::map<size_t, size_t> bucket_map_t;

// Associates polygon indices with map objects
typedef std::vector<rgn_t *> rgn_vec_t;

// Maps index of processed point to edge which it is the end of
typedef std::multimap<size_t, edge_t *> point_idx_to_edge_map_t;

typedef std::vector<size_t> int_vec_t;

class CGeneralizeLevel {
  public:
	CGeneralizeLevel (int_vec_t & _elementIndices, rgn_vec_t & _rgns, size_t _sLevel);
	size_t Do (size_t _startCount, size_t _totalCount);

  private:
	int_vec_t & m_ElementIndices;
	size_t m_cElements;
	const size_t m_cLevel;
	const double m_d, m_fE;

	std::vector<edges_t> m_tblEdges;
	int_set_t m_setProcessed;
	std::vector <size_t> m_vecProcessed;

	edge_buckets_t m_vecBuckets;
	bucket_map_t m_mapBuckets;
	rgn_vec_t & m_Rgns;
	point_idx_to_edge_map_t m_mapProcessedEdges;

	// (point index) -> (adjacent polygon index, adjacent point index, point type) ...
	vec_point_to_element_t m_vecPointToElement;

	rgn_element_t & getElement (size_t _cIndex) {
		return m_Rgns [_cIndex]->elements [m_ElementIndices [_cIndex]];
	}

	void GeneralizeElement (size_t _cIndex);
	void CopyProcessedEdges (size_t _cElementIndex, edges_t & _edges, int_set_t & _junctions);
	void GenerateEdges (const int_set_t & _junctions, edges_t & _edges);
	void ProcessEdges (rgn_element_t & _element, int_set_t & _junctions, const edges_t & _edges, size_t _cIndex);
	void CopySinglePoints (const edges_t & _edges, size_t _cPolygonIdx, size_t _cPointIdx, size_t _cDelta);
	bool IsProcessed (size_t _cPoint) const {
		return m_setProcessed.find (_cPoint) != m_setProcessed.end ();
	}

	edge_t * InsertStitchingEdge (size_t _cPolyIdx, size_t _cStart, size_t _cEnd,
		 size_t _cAdjPolyIdx, size_t _cAdjStart, size_t _cAdjEnd);
	void StitchBucket (edge_bucket_t & _bucket);
	void NormalizeEdges (edge_pair_t & _edges);
	void NormalizeBucket (edge_bucket_t & _bucket);
	void GlobalStitch ();
	edge_bucket_t::iterator MergePolygons (edge_bucket_t & _bucket, edge_bucket_t::iterator _iEdges);

public:
	size_t m_cDeletedPoints;
};

typedef std::map<size_t, int_vec_t> translate_map_t;

class CTranslateIndices {
public:
	CTranslateIndices (size_t _cPolygonIdx, CGeneralizeLevel & _generalize) :
		m_cPolygonIdx (_cPolygonIdx), m_generalize (_generalize) {}

	void swap (CTranslateIndices & _rhs) {
		m_mapIndices.swap (_rhs.m_mapIndices);
		std::swap (m_cPolygonIdx, _rhs.m_cPolygonIdx);
	}

	void DefinePoly (size_t _cIdx, size_t _cCount);
	void Define (size_t _cIdx, size_t _cStart, size_t _cEnd, size_t _cNewStart,
		size_t _cNewEnd, bool _bLastPointIs0 = false);
	void TranslateEdges (edge_bucket_t::iterator _iStart, edge_bucket_t::iterator _iEnd,
		size_t _cNewPoints);
	void TranslateEdge (edge_t & _edge);

	translate_map_t m_mapIndices;
	size_t m_cPolygonIdx;
	CGeneralizeLevel & m_generalize;
};

bool EdgePairLess (const edge_pair_t & _lhs, const edge_pair_t & _rhs) {
	if (_lhs.first.cPolygonIndex < _rhs.first.cPolygonIndex)
		return true;

	if (_lhs.first.cPolygonIndex > _rhs.first.cPolygonIndex)
		return false;

	if (_lhs.first.cStartPoint == _lhs.second.cStartPoint ||
		_lhs.first.cEndPoint == _lhs.second.cEndPoint ||
		_lhs.first.cStartPoint == _lhs.second.cEndPoint ||
		_lhs.first.cEndPoint == _lhs.second.cStartPoint)
		return true;

	return _lhs.first.cStartPoint < _rhs.first.cStartPoint;
}

void CTranslateIndices::DefinePoly (size_t _cIdx, size_t _cCount) {
	int_vec_t & vecIndices = m_mapIndices [_cIdx];

	vecIndices.assign ((const size_t) _cCount, (const size_t) -1);
}

void CTranslateIndices::Define (size_t _cIdx, size_t _cStart, size_t _cEnd,
								size_t _cNewStart, size_t _cNewEnd, bool _bLastPointIs0) {
	int_vec_t & vecIndices = m_mapIndices [_cIdx];
	bool bReverse = _cNewStart > _cNewEnd;

	assert (abs ((int)((int) _cEnd - _cStart)) == abs ((int)((int) _cNewEnd - _cNewStart)));

	assert (_cEnd < vecIndices.size ());

	for (size_t cIdx = 0; cIdx <= _cEnd - _cStart; ++ cIdx)
		vecIndices [_cStart + cIdx] = _cNewStart + (bReverse ? -1*cIdx : cIdx);

	if (_bLastPointIs0)
		vecIndices [bReverse ? _cStart : _cEnd] = 0;
}

void CTranslateIndices::TranslateEdges (edge_bucket_t::iterator _iStart,
										edge_bucket_t::iterator _iEnd,
										size_t _cNewPoints) {
	if (m_mapIndices.size () == 0)
		return;

	for (edge_bucket_t::iterator iEdges = _iStart; iEdges != _iEnd; ++ iEdges)	{
		edge_t oldFirst = iEdges->first;
		edge_t second = iEdges->second;

		TranslateEdge (iEdges->first);
		TranslateEdge (iEdges->second);

		edge_t newFirst = iEdges->first;
		edge_t newSecond = iEdges->second;

		if (iEdges->first.cPolygonIndex != m_cPolygonIdx)
			continue;

		// Fix endpoint indices
		if ((newFirst.cEndPoint < newFirst.cStartPoint &&
				! (newFirst.cEndPoint == 0 && newFirst.cStartPoint == _cNewPoints - 1)) ||
				(newFirst.cStartPoint == 0 && newFirst.cEndPoint == _cNewPoints - 1 &&
				oldFirst.cEndPoint - oldFirst.cStartPoint != _cNewPoints)) {
			std::swap (iEdges->first.cStartPoint, iEdges->first.cEndPoint);
			std::swap (iEdges->second.cEndPoint, iEdges->second.cEndPoint);
		}
	}
}

void CTranslateIndices::TranslateEdge (edge_t & _edge) {
	translate_map_t::iterator iVec = m_mapIndices.find (_edge.cPolygonIndex);

	if (iVec == m_mapIndices.end ())
		return;

	assert (_edge.cStartPoint < iVec->second.size ());
	assert (_edge.cEndPoint < iVec->second.size ());

	size_t cNewStart = iVec->second [_edge.cStartPoint];
	size_t cNewEnd = iVec->second [_edge.cEndPoint];

	if (cNewStart == (size_t) -1 || cNewEnd == (size_t) -1)
		return;

	_edge.cStartPoint = cNewStart;
	_edge.cEndPoint = cNewEnd;
	_edge.cPolygonIndex = m_cPolygonIdx;
}

CGeneralizeLevel::CGeneralizeLevel (int_vec_t & _elementIndices, rgn_vec_t & _rgns, size_t _cLevel) :
		m_ElementIndices (_elementIndices),
		m_cElements (_elementIndices.size ()),
		m_Rgns (_rgns),
		m_d (GetGeneralizationThreshold (_cLevel)),
		m_fE (1e-6),
		m_cDeletedPoints (0),
		m_cLevel (_cLevel) {
	m_tblEdges.resize (m_cElements);
}

template <class _Iterator>
void CopyPoints (points_t & _dest, _Iterator _begin, _Iterator _end,
				 CTranslateIndices & _translator, size_t _cPolyIdx,
				 size_t _cRangeStart, size_t _cRangeEnd,
				 bool _bReverse, bool _bAddEndPoint, bool _bLastPointIs0) {
	size_t cNewStart = _dest.size ();

	_dest.insert (_dest.end (), _begin, _end);

	size_t cNewEnd = _dest.size () - (_bAddEndPoint ? 0 : 1);

	assert (cNewStart <= cNewEnd);

	if (_bReverse)
		std::swap (cNewStart, cNewEnd);

	_translator.Define (_cPolyIdx, _cRangeStart, _cRangeEnd, cNewStart, cNewEnd, _bLastPointIs0);
}

edge_bucket_t::iterator CGeneralizeLevel::MergePolygons (edge_bucket_t & _bucket,
														 edge_bucket_t::iterator _iEdges) {
	edge_t & first = _iEdges->first;
	edge_t & second = _iEdges->second;
	rgn_element_t & elemFirst = getElement (first.cPolygonIndex);
	rgn_element_t & elemSecond = getElement (second.cPolygonIndex);
	points_t & pnt1st = elemFirst.points;
	points_t & pnt2nd = elemSecond.points;
	size_t cPnts1 = pnt1st.size ();
	size_t cPnts2 = pnt2nd.size ();
	edge_bucket_t::iterator iNext = _iEdges;

	++ iNext;

	std::vector<point_t> points;
	size_t cNewPointCount = cPnts1 + cPnts2 - 2;

	CTranslateIndices translator (first.cPolygonIndex, * this);

	bool bValid = true;

	bValid = bValid && (first.cStartPoint < first.cEndPoint || (first.cEndPoint == 0 && first.cStartPoint == cPnts1 - 1));
	bValid = bValid && (first.cStartPoint < cPnts1);
	bValid = bValid && (first.cEndPoint < cPnts1);
	bValid = bValid && (second.cStartPoint < cPnts2);
	bValid = bValid && (second.cEndPoint < cPnts2);
	bValid = bValid && PointContainsPt (pnt1st [first.cStartPoint], pnt2nd [second.cStartPoint], m_fE, g_map.fCosY);
	bValid = bValid && PointContainsPt (pnt1st [first.cEndPoint], pnt2nd [second.cEndPoint], m_fE, g_map.fCosY);

	if (! bValid)
		return iNext;

	translator.DefinePoly (first.cPolygonIndex, cPnts1);

	if (first.cPolygonIndex == second.cPolygonIndex) {
		if (first.cStartPoint != second.cStartPoint && first.cEndPoint != second.cEndPoint) {
			// 0th point could be either on outer or on inner contour
			if (first.cEndPoint > second.cStartPoint ||
				(first.cStartPoint == cPnts1 - 1 && first.cEndPoint == 0)) {
				std::swap (first.cStartPoint, first.cEndPoint);
				std::swap (second.cStartPoint, second.cEndPoint);
				std::swap (first, second);
			}

			size_t cNewElement = m_cElements;
			points_t newPoints;

			newPoints.insert (newPoints.end (), pnt1st.begin () + first.cEndPoint,
				pnt1st.begin () + second.cEndPoint);

			// If true, 0th point is on inner contour
			bool bShouldSwap = PolygonContainsPt (newPoints, pnt1st [0]) == 1;

			CTranslateIndices newTranslator (cNewElement, * this);
			newTranslator.DefinePoly (first.cPolygonIndex, cPnts1);

			newTranslator.Define (first.cPolygonIndex, first.cEndPoint, second.cEndPoint,
				0, second.cEndPoint - first.cEndPoint, true);

			points.insert (points.end (), pnt1st.begin (), pnt1st.begin () + first.cStartPoint);
			translator.Define (first.cPolygonIndex, 0, first.cStartPoint, 0, first.cStartPoint, second.cStartPoint == 0);

			if (second.cStartPoint > 0) {
				points.insert (points.end (), pnt1st.begin () + second.cStartPoint, pnt1st.end ());
				translator.Define (first.cPolygonIndex, second.cStartPoint, cPnts1 - 1,
					first.cStartPoint, cPnts1 - (second.cStartPoint - first.cStartPoint) - 1);
			}

			if (bShouldSwap) {
				points.swap (newPoints);
				translator.swap (newTranslator);
				std::swap (translator.m_cPolygonIdx, newTranslator.m_cPolygonIdx);
			}

			newTranslator.TranslateEdges (iNext, _bucket.end (), newPoints.size ());

			rgn_t & rgn = * m_Rgns [first.cPolygonIndex];

			rgn.elements.push_back (rgn_element_t ());

			rgn_element_t & elem = rgn.elements.back ();

			++ m_cElements;
			m_ElementIndices.push_back (rgn.elements.size () - 1);
			m_Rgns.push_back (& rgn);
			elem.bHole = true;
			elem.cLevel = m_cLevel;
			elem.cFileOffset = (size_t) -1;
			elem.points.assign (newPoints.begin (), newPoints.end ());
		} else {
			if (first.cEndPoint != second.cEndPoint) {
				std::swap (first.cStartPoint, first.cEndPoint);
				std::swap (second.cStartPoint, second.cEndPoint);
				std::swap (first, second);
				assert (first.cEndPoint == 0 || first.cStartPoint < first.cEndPoint);
			}

			if (first.cEndPoint == 0 || first.cEndPoint == cPnts1 - 1) {
				points.insert (points.end (), pnt1st.begin () + second.cStartPoint, pnt1st.begin () + first.cStartPoint);
				translator.Define (first.cPolygonIndex, second.cStartPoint, first.cStartPoint,
					0, first.cStartPoint - second.cStartPoint, true);
			} else {
				points.insert (points.end (), pnt1st.begin (), pnt1st.begin () + first.cStartPoint);
				translator.Define (first.cPolygonIndex, 0, first.cStartPoint, 0, first.cStartPoint);

				points.insert (points.end (), pnt1st.begin () + second.cStartPoint, pnt1st.end ());
				translator.Define (first.cPolygonIndex, second.cStartPoint, cPnts1 - 1,
					first.cStartPoint, cPnts1 - 1 - (second.cStartPoint - first.cStartPoint));
			}
		}
	} else if (cPnts1 == cPnts2 && first.cStartPoint == 0 && first.cEndPoint == cPnts1 - 1 &&
			second.cStartPoint == first.cStartPoint && second.cEndPoint == first.cEndPoint) {
		// Objects are duplicates
		return iNext;
	} else {
		translator.DefinePoly (second.cPolygonIndex, cPnts2);

		if (first.cEndPoint == 0 && first.cStartPoint == cPnts1 - 1) {
			// First edge connects last and 0th point of the first polygon
			if (second.cStartPoint == 0 && second.cEndPoint == cPnts2 - 1) {
				// Co-oriented, 0th point of 1st polygon is the last point of 2nd polygon (and vice versa)
				points.insert (points.end (), pnt1st.begin (), pnt1st.end () - 1);
				translator.Define (first.cPolygonIndex, 0, points.size (),
					0, points.size ());

				points.insert (points.end (), pnt2nd.begin (), pnt2nd.end () - 1);

				translator.Define (second.cPolygonIndex, 0, cPnts2 - 1, cPnts1 - 1,
					cNewPointCount, true);
			} else if (second.cStartPoint == cPnts2 - 1 && second.cEndPoint == 0) {
				// Counter-oriented, 0th and last points are shared between polygons
				points.insert (points.end (), pnt1st.begin (), pnt1st.end () - 1);
				translator.Define (first.cPolygonIndex, 0, points.size (),
					0, points.size ());

				points.insert (points.end (), pnt2nd.rbegin (), pnt2nd.rend () - 1);

				translator.Define (second.cPolygonIndex, 0, cPnts2 - 1, cNewPointCount,
					cPnts1 - 1, true);
			} else if (second.cEndPoint < second.cStartPoint) {
				// Co-oriented
				points.insert (points.end (), pnt1st.begin (), pnt1st.end () - 1);
				translator.Define (first.cPolygonIndex, 0, points.size (),
					0, points.size ());

				points.insert (points.end (), pnt2nd.begin () + second.cStartPoint, pnt2nd.end ());

				assert (cPnts1 - 2 + cPnts2 - second.cStartPoint < cNewPointCount);
				translator.Define (second.cPolygonIndex, second.cStartPoint, cPnts2 - 1,
					cPnts1 - 1, cPnts1 - 2 + cPnts2 - second.cStartPoint);

				points.insert (points.end (), pnt2nd.begin (), pnt2nd.begin () + second.cEndPoint);

				assert (cPnts1 + cPnts2 - second.cStartPoint - 1 <= cNewPointCount);
				translator.Define (second.cPolygonIndex, 0, second.cEndPoint,
					cPnts1 + cPnts2 - second.cStartPoint - 1, cNewPointCount, true);
			} else {
				// Counter-oriented
				points.insert (points.end (), pnt1st.begin (), pnt1st.end () - 1);
				translator.Define (first.cPolygonIndex, 0, points.size (),
					0, points.size ());

				points.insert (points.end (), pnt2nd.rend () - second.cStartPoint - 1, pnt2nd.rend ());

				assert (cPnts1 + second.cStartPoint - 1 < cNewPointCount);
				translator.Define (second.cPolygonIndex, 0, second.cStartPoint,
					cPnts1 + second.cStartPoint - 1, cPnts1 - 1);
				points.insert (points.end (), pnt2nd.rbegin (), pnt2nd.rend () - second.cEndPoint - 1);

				assert (cPnts1 + second.cStartPoint <= cNewPointCount);
				translator.Define (second.cPolygonIndex, second.cEndPoint, cPnts2 - 1,
					cNewPointCount, cPnts1 + second.cStartPoint, true);
			}
		} else if (second.cStartPoint == 0 && second.cEndPoint == cPnts2 - 1) {
			// Co-oriented, ends of 2nd polygon lie somewhere on the 1st polygon
			points.insert (points.end (), pnt1st.begin (), pnt1st.begin () + first.cStartPoint);
			translator.Define (first.cPolygonIndex, 0, first.cStartPoint, 0, first.cStartPoint);

			points.insert (points.end (), pnt2nd.begin (), pnt2nd.end () - 1);

			assert (first.cStartPoint + cPnts2 - 1 < cNewPointCount);
			translator.Define (second.cPolygonIndex, 0, cPnts2 - 1,
				first.cStartPoint, first.cStartPoint + cPnts2 - 1);

			points.insert (points.end (), pnt1st.begin () + first.cEndPoint, pnt1st.end ());

			assert (first.cStartPoint + cPnts2 - 1 < cNewPointCount);
			translator.Define (first.cPolygonIndex, first.cEndPoint, cPnts1 - 1,
				first.cStartPoint + cPnts2 - 1, cNewPointCount - 1);
		} else if (second.cStartPoint == cPnts2 - 1 && second.cEndPoint == 0) {
			// Counter-oriented, ends of 2nd polygon lie somewhere on the 1st polygon
			CopyPoints (points, pnt1st.begin (), pnt1st.begin () + first.cStartPoint,
				translator, first.cPolygonIndex, 0, first.cStartPoint, false, true, false);
			CopyPoints (points, pnt2nd.rbegin (), pnt2nd.rend () - 1,
				translator, second.cPolygonIndex, 0, cPnts2 - 1, true, true, false);
			CopyPoints (points, pnt1st.begin () + first.cEndPoint, pnt1st.end (),
				translator, first.cPolygonIndex, first.cEndPoint, cPnts1 - 1, false, false, false);
		} else if (second.cEndPoint < second.cStartPoint) {
			// Co-oriented (generic)
			CopyPoints (points, pnt1st.begin (), pnt1st.begin () + first.cStartPoint,
				translator, first.cPolygonIndex, 0, first.cStartPoint, false, true, false);
			CopyPoints (points, pnt2nd.begin () + second.cStartPoint, pnt2nd.end (),
				translator, second.cPolygonIndex, second.cStartPoint, cPnts2 - 1, false, false, false);
			CopyPoints (points, pnt2nd.begin (), pnt2nd.begin () + second.cEndPoint,
				translator, second.cPolygonIndex, 0, second.cEndPoint, false, true, false);
			CopyPoints (points, pnt1st.begin () + first.cEndPoint, pnt1st.end (),
				translator, first.cPolygonIndex, first.cEndPoint, cPnts1 - 1, false, false, false);
		} else {
			// Counter-oriented (generic)
			CopyPoints (points, pnt1st.begin (), pnt1st.begin () + first.cStartPoint,
				translator, first.cPolygonIndex, 0, first.cStartPoint, false, true, false);
			CopyPoints (points, pnt2nd.rend () - second.cStartPoint - 1, pnt2nd.rend (),
				translator, second.cPolygonIndex, 0, second.cStartPoint, true, false, false);
			CopyPoints (points, pnt2nd.rbegin (), pnt2nd.rend () - second.cEndPoint - 1,
				translator, second.cPolygonIndex, second.cEndPoint, cPnts2 - 1, true, true, false);
			CopyPoints (points, pnt1st.begin () + first.cEndPoint, pnt1st.end (),
				translator, first.cPolygonIndex, first.cEndPoint, cPnts1 - 1, false, false, false);
		}
	}

	translator.TranslateEdges (iNext, _bucket.end (), points.size ());

	if (g_map.cMaxPointsInElement < points.size ())
        g_map.cMaxPointsInElement = points.size ();

	getElement (first.cPolygonIndex).points.assign (points.begin (), points.end ());
	getElement (first.cPolygonIndex).rectBound.Extend (getElement (second.cPolygonIndex).rectBound);
	
	if (first.cPolygonIndex != second.cPolygonIndex)
		getElement (second.cPolygonIndex).bDeleted = true;

	return iNext;
}

void CGeneralizeLevel::StitchBucket (edge_bucket_t & _bucket) {
	NormalizeBucket (_bucket);

	std::set<rgn_t *> affetctedRgns;
	int_set_t affectedElements;
	size_t lastElem = (size_t) -1;

	for (edge_bucket_t::iterator iEdges = _bucket.begin (); iEdges != _bucket.end ();) {
		size_t cElem1 = iEdges->first.cPolygonIndex;
		size_t cElem2 = iEdges->second.cPolygonIndex;

		lastElem = cElem1;

		affectedElements.insert (cElem1);
		affectedElements.insert (cElem2);

		affetctedRgns.insert (m_Rgns [cElem1]);
		affetctedRgns.insert (m_Rgns [cElem2]);

		iEdges = MergePolygons (_bucket, iEdges);
	}

	if (lastElem == (size_t) -1)
		return;

	rgn_t & destRgn = * m_Rgns [lastElem];

	for (size_t cElem = 0; cElem < m_ElementIndices.size (); ++ cElem) {
		rgn_t * pRgn = m_Rgns [cElem];
		rgn_element_t & elem = getElement (cElem);

		if (pRgn == & destRgn || elem.bDeleted || affetctedRgns.find (pRgn) == affetctedRgns.end ())
			continue;

		destRgn.elements.push_back (elem);
		elem.bDeleted = true;
		m_Rgns [cElem] = & destRgn;
		m_ElementIndices [cElem] = destRgn.elements.size () - 1;
	}

	for (std::set<rgn_t *>::iterator iRgn = affetctedRgns.begin (); iRgn != affetctedRgns.end (); ++ iRgn)
		(* iRgn)->RefreshAttributes(g_map, false);
}

void CGeneralizeLevel::NormalizeEdges (edge_pair_t & _edges) {
	if (_edges.second.cPolygonIndex < _edges.first.cPolygonIndex) {
		std::swap (_edges.first, _edges.second);

		size_t cPoints1 = getElement (_edges.first.cPolygonIndex).points.size ();
		size_t cPoints2 = getElement (_edges.second.cPolygonIndex).points.size ();

		bool bIsEndSegment = ((_edges.second.cStartPoint == cPoints2 - 1 &&
				_edges.second.cEndPoint == 0) || _edges.second.cEndPoint - _edges.second.cStartPoint == 1) &&
				((_edges.first.cStartPoint == 0 && _edges.first.cEndPoint == cPoints1 - 1) ||
				(_edges.first.cStartPoint == cPoints1 - 1 && _edges.first.cEndPoint == 0));

		if (bIsEndSegment != (_edges.first.cStartPoint > _edges.first.cEndPoint)) {
			std::swap (_edges.first.cStartPoint, _edges.first.cEndPoint);
			std::swap (_edges.second.cStartPoint, _edges.second.cEndPoint);
		}
	}
}

void CGeneralizeLevel::NormalizeBucket (edge_bucket_t & _bucket) {
	for (edge_bucket_t::iterator iEdges = _bucket.begin ();
			iEdges != _bucket.end (); ++ iEdges)
		NormalizeEdges (* iEdges);
}

void CGeneralizeLevel::GlobalStitch () {
	for (size_t cBucket = 0; cBucket < m_vecBuckets.size (); ++ cBucket)
		StitchBucket (m_vecBuckets [cBucket]);
}

edge_t * CGeneralizeLevel::InsertStitchingEdge (size_t _cPolyIdx, size_t _cStart, size_t _cEnd,
											size_t _cAdjPolyIdx, size_t _cAdjStart,
											size_t _cAdjEnd) {
	rgn_t & rgn = * m_Rgns [_cPolyIdx];
	rgn_t & adjRgn = * m_Rgns [_cAdjPolyIdx];

	if (! rgn.IsPolygon () || ! adjRgn.IsPolygon () ||
			rgn.ushType != adjRgn.ushType || ! (rgn.strLabel == adjRgn.strLabel) ||
			getElement (_cPolyIdx).bHole != getElement (_cAdjPolyIdx).bHole)
		return NULL;

	bucket_map_t::iterator i1stBucket = m_mapBuckets.find (_cPolyIdx);
	bucket_map_t::iterator i2ndBucket = m_mapBuckets.find (_cAdjPolyIdx);

	size_t c1stBucket = i1stBucket != m_mapBuckets.end () ? i1stBucket->second : (size_t) -1;
	size_t c2ndBucket = i2ndBucket != m_mapBuckets.end () ? i2ndBucket->second : (size_t) -1;

	size_t cBucket = (size_t) -1;

	if (c1stBucket == (size_t) -1 && c2ndBucket == (size_t) -1) {
		cBucket = m_vecBuckets.size ();
		m_vecBuckets.resize (m_vecBuckets.size () + 1);
		m_mapBuckets [_cPolyIdx] = cBucket;
		m_mapBuckets [_cAdjPolyIdx] = cBucket;
	} else if (c1stBucket == (size_t) -1) {
		cBucket = c2ndBucket;
		m_mapBuckets [_cPolyIdx] = cBucket;
	} else if (c2ndBucket == (size_t) -1) {
		cBucket = c1stBucket;
		m_mapBuckets [_cAdjPolyIdx] = cBucket;
	} else if (c1stBucket != c2ndBucket) {
		// merge second bucket with first
		edge_bucket_t & bucket = m_vecBuckets [c1stBucket];
		edge_bucket_t & adjBucket = m_vecBuckets [c2ndBucket];

		bucket.insert (bucket.end (), adjBucket.begin (), adjBucket.end ());
		adjBucket.clear ();

		for (bucket_map_t::iterator iBucket = m_mapBuckets.begin ();
				iBucket != m_mapBuckets.end (); ++ iBucket)
			if (iBucket->second == c2ndBucket)
				iBucket->second = c1stBucket;

		cBucket = c1stBucket;
	} else
		cBucket = c1stBucket;

	m_vecBuckets [cBucket].push_back (std::make_pair (
		edge_t (_cPolyIdx, _cStart, _cEnd),
		edge_t (_cAdjPolyIdx, _cAdjStart, _cAdjEnd)));

	return & m_vecBuckets [cBucket].back ().first;
}

size_t CGeneralizeLevel::Do (size_t _cStartCount, size_t _cTotalCount) {
	m_cDeletedPoints = 0;

	assert (_cTotalCount != 0);

	for (size_t c = 0; c < m_cElements; ++ c) {
		GeneralizeElement (c);
		SetProgressStatus ((_cStartCount + c + 1)*100/_cTotalCount);
	}

	GlobalStitch ();

	return m_cDeletedPoints;
}

void CGeneralizeLevel::GeneralizeElement (size_t _cIndex) {
	rgn_element_t & element = getElement (_cIndex);
	int_set_t junctions;
	const points_t & points = element.points;
	edges_t & edges = m_tblEdges [_cIndex];

	m_setProcessed.clear ();
	m_vecProcessed.assign (points.size (), 1);
	m_mapProcessedEdges.clear ();

	CopyProcessedEdges (_cIndex, edges, junctions);

	const size_t cPoints = points.size ();

	m_vecPointToElement.clear ();
	m_vecPointToElement.resize (cPoints);

	for (size_t j = _cIndex + 1; j < m_cElements; ++ j) {
		if (! getElement (j).rectBound.Intersects (element.rectBound))
			continue;

		const rgn_element_t & neighbour = getElement (j);
		const points_t & otherPoints = neighbour.points;
		const size_t cOtherPoints = otherPoints.size ();
		size_t cOtherPoint = (size_t) -1;
		size_t cPrevPoint  = (size_t) -1;
		size_t cLastPoint  = (size_t) -1;
		int nDirection = 0;

		for (size_t cPoint = 0; cPoint < cPoints;
				cPoint += m_vecProcessed [cPrevPoint = cPoint]) {
			const point_t & point = points [cPoint];

			if (cOtherPoint != (size_t) -1) {
				if (m_vecProcessed [cPrevPoint] == 1) {
					// No points skipped.
					bool bNewDirection = false;
					if (nDirection == 0) {
						// Determine direction.
						if (
							cOtherPoint + 1 < cOtherPoints &&
							PointContainsPt (point, otherPoints [cOtherPoint + 1], m_fE, g_map.fCosY)
						)
							nDirection = 1;
						else if (
							cOtherPoint > 0 &&
							PointContainsPt (point, otherPoints [cOtherPoint - 1], m_fE, g_map.fCosY)
						)
							nDirection = -1;

						bNewDirection = nDirection != 0;
					}

					cOtherPoint += nDirection;

					bool bValidIdx = bNewDirection ||
						(cOtherPoint < cOtherPoints && cOtherPoint != (size_t) -1);

					if (
						bValidIdx && neighbour.pExtra &&
						! neighbour.pExtra->PointExtras [cOtherPoint].empty ()
					)
						junctions.insert (cPoint);

					if (
						nDirection != 0 && (
							bNewDirection || (
								bValidIdx && 
								PointContainsPt (point, otherPoints [cOtherPoint], m_fE, g_map.fCosY)
							)
						)
					) {
						m_vecPointToElement [cLastPoint = cPoint].push_back (
							point_rec_t (j, cOtherPoint));
						continue;
					}
				}
				
				assert (cLastPoint != (size_t) -1);
				point_rec_t & lastPoint = m_vecPointToElement [cLastPoint].back ();
				lastPoint.type = lastPoint.type == ptSTART_POINT ? ptSINGLE_POINT : ptEND_POINT;
				junctions.insert (cPrevPoint);
				cOtherPoint = (size_t) -1;
			}

			if (element.pExtra && ! element.pExtra->PointExtras [cPoint].empty ())
				junctions.insert (cPoint);

			if (! neighbour.rectBound.Contains (point))
				// Point is out of neighbour's bounding rect.
				continue;

			cOtherPoint = PointsContainPt (otherPoints, point, m_fE, g_map.fCosY);

			if (cOtherPoint != (size_t) -1) {
				nDirection = 0;
				junctions.insert (cPoint);
				m_vecPointToElement [cLastPoint = cPoint].push_back (
					point_rec_t (j, cOtherPoint, ptSTART_POINT));
			}
		}

		if (cLastPoint != (size_t) -1) {
			point_rec_t & lastPoint = m_vecPointToElement [cLastPoint].back ();
			if (lastPoint.type == ptNONE) {
				lastPoint.type = ptEND_POINT;
				junctions.insert (cLastPoint);
			} else if (lastPoint.type == ptSTART_POINT)
				lastPoint.type = ptSINGLE_POINT;
		}
	}

	GenerateEdges (junctions, edges);
	ProcessEdges (element, junctions, edges, _cIndex);
}

void CGeneralizeLevel::CopyProcessedEdges (
	size_t _cElementIndex,
	edges_t & _edges,
	int_set_t & _junctions
) {
	rgn_element_t & element = getElement (_cElementIndex);
	points_t & points = element.points;
	points_t tmpPoints (points);
	size_t cDelta = 0, cOld = 0;
	std::vector<point_extra_t> tmpExtraPoints;
	std::map<size_t, size_t> mapStartPoint;
	std::map<size_t, size_t> mapAdjStartPoint;

	if (element.pExtra)
		tmpExtraPoints.assign (
			element.pExtra->PointExtras.begin (),
			element.pExtra->PointExtras.end ()
		);

	for (edges_t::const_iterator iEdge = _edges.begin (); iEdge != _edges.end (); ++ iEdge) {
		int_pair_t segment = iEdge->first;
		const edge_t & edge = iEdge->second;

		if (segment.second < cOld)
			continue;

		if (segment.first < cOld)
			segment.first = cOld;

		cOld = segment.second;

		if (edge.cStartPoint == edge.cEndPoint) {
			assert (segment.first == segment.second);
			_junctions.insert (segment.first - cDelta);

			size_t cAdjPoints = getElement (edge.cPolygonIndex).points.size ();
			std::map<size_t, size_t>::iterator iIdx;

			if (segment.first == 0)
				mapStartPoint [edge.cPolygonIndex] = edge.cStartPoint;
			else if (
						segment.second == points.size () - 1 &&
						(iIdx = mapStartPoint.find (edge.cPolygonIndex)) != mapStartPoint.end ()
			) {
				if (
						(edge.cStartPoint == 0 && iIdx->second == cAdjPoints - 1) ||
						(edge.cStartPoint == cAdjPoints - 1 && iIdx->second == 0) ||
						(fabs ((float)((int) edge.cStartPoint - (int) iIdx->second)) == 1)
				) {
					edge_t * pEdge = InsertStitchingEdge (
						_cElementIndex, segment.first - cDelta, 0,
						edge.cPolygonIndex, edge.cStartPoint, iIdx->second);

					if (pEdge)
						m_mapProcessedEdges.insert (std::make_pair (pEdge->cEndPoint, pEdge));
				} else
					iIdx->second = edge.cStartPoint;
			} else if (edge.cStartPoint== 0 || edge.cStartPoint == cAdjPoints - 1) {
				iIdx = mapAdjStartPoint.find (edge.cPolygonIndex);

				if (
						iIdx != mapAdjStartPoint.end() &&
						fabs ((float)((int) segment.first - (int) iIdx->second)) == 1
				) {
					edge_t * pEdge = InsertStitchingEdge (
						_cElementIndex, iIdx->second, segment.first - cDelta,
						edge.cPolygonIndex, edge.cStartPoint ? 0 : cAdjPoints - 1, edge.cStartPoint);

					if (pEdge) {
						m_mapProcessedEdges.insert (std::make_pair (pEdge->cEndPoint, pEdge));
						m_setProcessed.insert (pEdge->cEndPoint);
					}
				} else
					mapAdjStartPoint [edge.cPolygonIndex] = segment.first - cDelta;
			}

			continue;
		}

		size_t cAdjStartPoint = edge.cStartPoint;
		size_t cAdjEndPoint   = edge.cEndPoint;
		const bool bReverse = edge.cEndPoint < edge.cStartPoint;

		if (bReverse)
			std::swap (cAdjStartPoint, cAdjEndPoint);

		if (segment.second - segment.first < cAdjEndPoint - cAdjStartPoint)
			continue;

		assert (segment.second - segment.first >= cAdjEndPoint - cAdjStartPoint);

		const size_t cStartPoint = segment.first - cDelta;
		const size_t cEndPoint   = segment.second - cDelta;
		const points_t & adjPoints = getElement (edge.cPolygonIndex).points;
		const points_t::iterator dest = tmpPoints.begin () + cStartPoint;

		std::copy (
			adjPoints.begin () + cAdjStartPoint,
			adjPoints.begin () + cAdjEndPoint + 1,
			dest
		);

		const size_t cCount = (cEndPoint - cStartPoint) - (cAdjEndPoint - cAdjStartPoint);

		if (bReverse)
			std::reverse (tmpPoints.begin () + cStartPoint,
				tmpPoints.begin () + cEndPoint - cCount + 1);

		assert (cEndPoint < tmpPoints.size ());

		if (cCount > 0) {
			tmpPoints.erase (
				tmpPoints.begin () + cEndPoint - cCount + 1,
				tmpPoints.begin () + cEndPoint + 1
			);

			if (element.pExtra)
				tmpExtraPoints.erase (
					tmpExtraPoints.begin () + cEndPoint - cCount + 1,
					tmpExtraPoints.begin () + cEndPoint + 1
				);
		}

		m_cDeletedPoints += cCount;

		_junctions.insert (cStartPoint);
		_junctions.insert (cEndPoint - cCount);
		m_setProcessed.insert (cEndPoint - cCount);
		m_vecProcessed [cStartPoint] = cAdjEndPoint - cAdjStartPoint;

		if (bReverse)
			// swap back
			std::swap (cAdjStartPoint, cAdjEndPoint);

		edge_t * pEdge = InsertStitchingEdge (_cElementIndex, cStartPoint, cEndPoint - cCount,
			edge.cPolygonIndex, cAdjStartPoint, cAdjEndPoint);

		if (pEdge)
			m_mapProcessedEdges.insert (std::make_pair (pEdge->cEndPoint, pEdge));

		cDelta += cCount;
	}

	points.assign (tmpPoints.begin (), tmpPoints.end ());

	if (element.pExtra)
		element.pExtra->PointExtras.assign (tmpExtraPoints.begin (), tmpExtraPoints.end ());

	_edges.clear ();
}

void CGeneralizeLevel::GenerateEdges (const int_set_t & _junctions, edges_t & _edges) {
	size_t cPrevPoint = (size_t) -1;
	std::map<size_t, size_t> prevIndices; // polygon index -> point index

	for (int_set_t::const_iterator iJunction = _junctions.begin (); iJunction != _junctions.end (); ++ iJunction) {
		const size_t cPoint = * iJunction;
		const point_list_t & lstPoints = m_vecPointToElement [cPoint];

		for (point_list_t::const_iterator iPoint = lstPoints.begin (); iPoint != lstPoints.end (); ++ iPoint) {
			const bool bIsStartPoint =
				(iPoint->type == ptSTART_POINT || iPoint->type == ptEND_POINT) &&
				(prevIndices.find (iPoint->cPolygonIndex) == prevIndices.end ());

			assert ((cPrevPoint != (size_t) -1) || (iPoint->type != ptNONE));

			if (! bIsStartPoint) {
				if (iPoint->type == ptSINGLE_POINT)
					_edges.insert (
						std::make_pair (
							std::make_pair (cPoint, cPoint),
							edge_t (
								iPoint->cPolygonIndex,
								iPoint->cIndex,
								iPoint->cIndex
							)
						)
					);
				else {
					assert (prevIndices.find (iPoint->cPolygonIndex) != prevIndices.end ());
					_edges.insert (
						std::make_pair (
							std::make_pair (cPrevPoint, cPoint), // start/end point indices
							edge_t (
								iPoint->cPolygonIndex,
								prevIndices [iPoint->cPolygonIndex],
								iPoint->cIndex
							)
						)
					);
				}

				// It's an end point: removing stored point index.
				if (
					iPoint->type == ptSTART_POINT ||
					iPoint->type == ptEND_POINT
				)
					prevIndices.erase (iPoint->cPolygonIndex);
			}

			if (bIsStartPoint || iPoint->type == ptNONE)
				prevIndices [iPoint->cPolygonIndex] = iPoint->cIndex;
		}

		cPrevPoint = cPoint;
	}
}

void CGeneralizeLevel::CopySinglePoints (const edges_t & _edges, size_t _cPolygonIdx, size_t _cPointIdx, size_t _cDelta) {
	typedef edges_t::const_iterator iter_t;
	const std::pair<iter_t, iter_t> bounds = _edges.equal_range (std::make_pair (_cPointIdx, _cPointIdx));

	for (iter_t iEdge = bounds.first; iEdge != bounds.second; ++ iEdge) {
		const edge_t & edge = iEdge->second;

		assert (edge.cStartPoint == edge.cEndPoint);

		size_t cOwnPoint = _cPointIdx - _cDelta;
		const int_pair_t adjSegment = std::make_pair (edge.cStartPoint, edge.cEndPoint);
		edges_t & adjEdges = m_tblEdges [edge.cPolygonIndex];

		adjEdges.insert (std::make_pair (adjSegment, edge_t (_cPolygonIdx, cOwnPoint, cOwnPoint)));
	}
}

void CGeneralizeLevel::ProcessEdges (
	rgn_element_t & _element,
	int_set_t & _junctions,
	const edges_t & _edges,
	size_t _cIndex
) {
	points_t & points = _element.points;

	_junctions.insert (0);
	_junctions.insert (points.size () - 1);

	size_t cPrevPoint = 0;
	size_t cDelta = 0;
	std::map<size_t, int> deltas; // signed

	point_extras_t pointExtras;

	if (_element.pExtra) {
		pointExtras.resize (points.size ());
		pointExtras [0] = _element.pExtra->PointExtras [0];
	}

	CopySinglePoints (_edges, _cIndex, 0, 0);

	int_set_t::const_iterator iJunction = _junctions.begin ();
	for (++ iJunction; iJunction != _junctions.end (); ++ iJunction) {
		const size_t cPoint = * iJunction;

		if (! IsProcessed (cPoint)) {
			size_t cCount = GeneralizePart (points, cPrevPoint - cDelta, cPoint - cDelta, m_d, g_map.fCosY);

			// Copy edges.
			typedef edges_t::const_iterator iter_t;
			const int_pair_t segment = std::make_pair (cPrevPoint, cPoint);
			const std::pair<iter_t, iter_t> bounds = _edges.equal_range (segment);

			for (iter_t iEdge = bounds.first; iEdge != bounds.second; ++ iEdge) {
				const edge_t & edge = iEdge->second;
				const bool bReverse = edge.cStartPoint > edge.cEndPoint;

				size_t cStartPoint = cPrevPoint - cDelta;
				size_t cEndPoint   = cPoint - cDelta - cCount;
				size_t cAdjStartPoint = edge.cStartPoint;
				size_t cAdjEndPoint   = edge.cEndPoint;

				if (bReverse) {
					std::swap (cStartPoint, cEndPoint);
					std::swap (cAdjStartPoint, cAdjEndPoint);
				}

				const int_pair_t adjSegment = std::make_pair (cAdjStartPoint, cAdjEndPoint);
				edges_t & adjEdges = m_tblEdges [edge.cPolygonIndex];

				if (adjEdges.find (adjSegment) == adjEdges.end ())
					adjEdges.insert (std::make_pair (adjSegment, edge_t (_cIndex, cStartPoint, cEndPoint)));
			}

			m_cDeletedPoints += cCount;
			cDelta           += cCount;
		} else {
			typedef point_idx_to_edge_map_t::const_iterator I;
			std::pair<I, I> bounds = m_mapProcessedEdges.equal_range (cPoint);
			for (I iEdge = bounds.first; iEdge != bounds.second; ++ iEdge) {
				edge_t & edge = * iEdge->second;
				edge.cStartPoint -= cDelta;
				edge.cEndPoint -= cDelta;
			}
		}

		CopySinglePoints (_edges, _cIndex, cPoint, cDelta);

		if (_element.pExtra)
			pointExtras [cPoint - cDelta] = _element.pExtra->PointExtras [cPoint];

		cPrevPoint = * iJunction;
	}

	typedef point_idx_to_edge_map_t::const_iterator I;
	std::pair<I, I> bounds = m_mapProcessedEdges.equal_range (0);

	for (I iEdge = bounds.first; iEdge != bounds.second; ++ iEdge) {
		if (iEdge->second->cStartPoint == cPrevPoint) {
			iEdge->second->cStartPoint -= cDelta;
		}
	}

	if (_element.pExtra) {
		pointExtras.resize (points.size ());
		_element.pExtra->PointExtras.swap (pointExtras);
	}
}

void GeneralizeMap (size_t & _cDeletedPoints, size_t & _cDeletedElements,
					size_t & _cDeletedRgns) {
	std::vector<int_vec_t> vecLevels;
	std::vector<rgn_vec_t> vecRgns;
	size_t cElements = 0;
	size_t cKind;

	SetProgressStatus (0);

	for (cKind = rkPolygon; cKind >= rkPolyline; -- cKind) {
		layer_t & layer = g_map.layers [cKind];
		rgns_t & rgns = layer.rgns;
		
		for (rgns_t::iterator iRgn = rgns.begin (); iRgn != rgns.end (); ++ iRgn) {
			rgn_t & rgn = * iRgn;

			if (rgn.IsMutable ())
				for (size_t cElement = 0; cElement < rgn.elements.size (); ++ cElement) {
					rgn_element_t & element = rgn.elements [cElement];

					if (element.bDeleted)
						continue;

					if (size_t (element.cLevel) + 1 > vecLevels.size ()) {
						vecLevels.resize (element.cLevel + 1);
						vecRgns.resize (element.cLevel + 1);
					}

					float d = GetGeneralizationThreshold (element.cLevel);

					if (cKind > rkPolyline)
						d *= d;

					if (element.fLengthOrArea < d) {
						element.bDeleted = true;
						_cDeletedPoints += element.points.size ();
						++ _cDeletedElements;
					} else {
						++ cElements;
						vecLevels [element.cLevel].push_back (cElement);
						vecRgns [element.cLevel].push_back (& rgn);
					}
				}
		}
	}

	size_t cProcessed = 0;
	for (size_t cLevel = 0; cLevel < vecLevels.size (); ++ cLevel) {
		CGeneralizeLevel generalizeLevel (vecLevels [cLevel], vecRgns [cLevel], cLevel);
		
		_cDeletedPoints += generalizeLevel.Do (cProcessed, cElements);
		cProcessed += vecLevels [cLevel].size ();
	}

	// delete empty objects
	for (cKind = rkPolyline; cKind <= rkPolygon; ++ cKind) {
		layer_t & layer = g_map.layers [cKind];
		rgns_t & rgns = layer.rgns;
		
		for (rgns_t::iterator iRgn = rgns.begin (); iRgn != rgns.end (); ++ iRgn) {
			rgn_t & rgn = * iRgn;

			if (rgn.IsImmutable ())
				continue;

			size_t cRgnElements = rgn.elements.size ();

			for (size_t cElement = 0; cElement < rgn.elements.size (); ++ cElement) {
				rgn_element_t & element = rgn.elements [cElement];

				if (cKind > rkPolyline && ! element.bDeleted && element.points.size () < 3) {
					element.bDeleted = true;
					++ _cDeletedElements;
					_cDeletedPoints += element.points.size ();
				}

				if (element.bDeleted)
					-- cRgnElements;
			}

			if (cRgnElements == 0) {
				rgn.Delete (g_map);
				++ _cDeletedRgns;
			}
		}
	}
}